package com.example.Arithmetic.Lettcode;

import java.util.LinkedList;

/**
 * 日期：2023/12/30
 * 时间：20:19
 * 描述：力扣518，零钱兑换
 * 给定数组，寻找数组元素组合目标值有多少种组合，递归解法
 */
public class E01Lettcode518 {
    public int change(int amount, int[] coins) {
        int[] i = new int[coins.length];
        int k = 0;
        for (int j = coins.length - 1; j >= 0; j--) {
            i[k] = coins[j];
            k++;
        }
        return rec(0, i, amount, new LinkedList<>(), true);
    }

    /**
     * 求凑成剩余金额的解的个数
     *
     * @param index  当前硬币索引
     * @param coins  硬币面值数组
     * @param amount 剩余金额
     * @param stack  -
     * @param first  -
     * @return 解的个数
     */
    private int rec(int index, int[] coins, int amount, LinkedList<Integer> stack, boolean first) {
//        情况1，剩余金额<1无解
//        情况2，剩余金额>1继续递归
//        情况1，剩余金额=1找到解
        if (!first) {
            stack.push(coins[index]);
        }
        int count = 0;
        if (amount < 0) {
            System.out.println("无解" + stack);
        } else if (amount == 0) {
            System.out.println("有解" + stack);
            count = 1;
        } else {
            for (int i = coins.length - 1; i >= index; i--) {
                count += rec(i, coins, amount - coins[i], stack, false);
            }
        }
        if (!stack.isEmpty()) {
            stack.pop();
        }
        return count;
    }

    public int change1(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        // System.out.println(Arrays.toString(dp));
        return dp[amount];
    }

    public static void main(String[] args) {
        E01Lettcode518 e01Lettcode518 = new E01Lettcode518();
        int change = e01Lettcode518.change(500, new int[]{1, 2, 5});

        int i = e01Lettcode518.change1(500, new int[]{1, 2, 5});
        System.out.println(i);
        System.out.println(change);
    }
}
